HW#2 --- last modified February 07 2019 04:20:37..

Solution set.

Due date: Oct 6

Files to be submitted:
  Hw2.zip

Purpose: To reason about the hill-climbing, simulated annealing, and genetic algorithms. To code the minimax algorithm with alpha-beta pruning in a specific context.

Related Course Outcomes:

The main course outcomes covered by this assignment are:

LO6 -- Students should be able to explain the advantages and disadvantages of hill climbing.

LO8 -- Students should be able to explain the advantages and disadvantages of alpha-beta pruning.

Specification:

This homework consists of a written component and a coding component. Files for both components should be submitted in your Hw2.zip file along with a readme.txt with any additional instructions, a list of your team mates and their IDs. For the written component I'd like you to come with concretely specified examples of the eight queens problem (i.e., specific boards and descriptions of how the algorithms would operate on those boards) which satisfy some criteria. For the first problem I want you to come up with an example of a board in which beam search with two starting points is will not give the same result as hill climbing with a single restart. For the some problem, I want you to come up with a schedule for use in our simulated annealing algorithm that could be used to solve the eight queens problem. For your schedule I want you to give an example of a situation where rather than going in the direction of a solution the algorithm goes from a better state to a less fit one.

For the coding portion of the assignment you are going to write a program that can play two person Crazy Eights. This is a two-person, zero-sum game with partial information. We assume the deck has 52 cards (no jokers). The cards are give the 0 - Ace of Spades, 1 - Two of Spades, .. 9 - 10 of Spades, 10 - Jack of Spades, 11 - Queen of Spades, 12 - King of Spades, 13 - Ace of Hearts, ..., 25 - King of Hearts, 26 Ace of Diamonds, ..., 38 - King of Diamonds, 39 - Ace of Clubs, ... 51 King of Clubs. At the start of the game both players get eight cards. From the remaining face-down deck a top card is flipped over to start a visible stack of cards. In a turn a player must either put a card down on top of the visible stack or take a card from the stack of face-down cards but not both. To put a card down, it must be either the same suit or the same number or an eight. So for example, on the 4 of Spades I can put the 4 of Heart, Clubs, or Diamonds or I could put any Spade or I could put any eight. The person who plays an eight calls out a new suit that the next card must be played in (unless the next player plays an eight). In addition to eight's, certain other cards of special properties: a Jack causes the other player to lose their turn, the Queen of Spades causes the other player to pick up five cards, finally, if a two is played then the other player has to pick up two, unless the other player plays a two on it, in which case the other player has to pick up four, unless they have a two in which case the other player picks up six, unless they have a two in which case the other player picks up eight. If a player has to pick up cards in a round, they are not allowed to play a card in that round. The object of Crazy Eights is to get rid of all your cards - the first person to do so wins. If there are no cards left in the unseen deck, then the game also ends. In this case for each player, the player with the least number of cards wins. If both players have the same number of cards then the player with the lowest number card by the above card numbering wins.

You will write your code in a file named crazy_eights.py. In this file you will have a Python Class CrazyEight. This class has to have the methods move(partial_state) and move_perfect_knowledge(state). A hand is a list of integers without repeats in the range between 0 and 51. A deck is a list of integers without repeats in the range between 0 and 51 representing the cards that are face down that have not been picked up by either player. A state is a Python tuple (deck, hand, partial_state) where the hand represents the other player's hand. A partial_state is a Python tuple (face_up_card, suit, hand, history). Here face_up_card is the current card on which the next move must be made. Suit is an integer among 0,1,2,3 where 0 - Spades, 1 - Hearts, 2 - Diamonds, or 3 -Clubs. In the event that the face_up_card is an eight this determines what the suit is. Hand in this case is the player's hand, and history represents all of the moves made so far. To be more specific, history is a Python list of moves. A move is a quadruple (player_num, face_up_card, suit, number_of_cards). player_num is 0 - yourself or 1 - other player and represents who made the move, face_up_card represents the face_up_card after the move, suit represents the next suit that must be played, number_of_cards indicates the number of cards picked up by the player (if any). As an example, at the start of the game the history might consist of a list of length 1 such as [(1, 7, 0, 0)]. This represents that the next player to move is 0, the face up card is the 7 of spades, and that in this initial non-move no one picked up a card. Suppose the next player plays a 2 of Spades and then after that the other player plays. The player after that must pick up two cards so we get:
[(1, 7, 0, 0), (0,1,0,0), (1, 0, 0, 2)].
The 2 in (1, 0, 0, 2) indicates two cards were picked up. Since when we pick up cards we are not allowed to play cards, the values 0, 0 are ignore and so the face up card is still the 2 of spades. If a Jack of Spades were then played and that player gets to play again a 6 of Spades, we'd have:
[(1, 7, 0, 0), (0,1,0,0), (1, 0, 0, 2), (0,10,0,0), (0, 5, 0, 0)].
Now if player 1 plays the 8 of Hearts and switches the suit to Diamonds we'd get:
[(1, 7, 0, 0), (0,1,0,0), (1, 0, 0, 2), (0,10,0,0), (0, 5, 0, 0), (1, 20, 2, 0)].

From a state (rather than a partial state), we have complete information about all the cards. We can thus imagine running the minimax algorithm out to a certain depth using alpha-beta pruning and some heuristic and choosing the best card to play accordingly. This is what the method move_perfect_knowledge(state) is supposed to do. It is supposed to return a move as defined above. The method move(partial_state) is supposed to have a for loop that cycles over trials (not all trials, but a decent number like a 100 to get statistics). In a trial, this method generates a random state which is consistent with the observed partial_state, it then calls move_perfect_knowledge(state) gets a move back and keeps a tally of it. After the for loop is done the move that was chosen the most is return by move(state).

You should code a driver program driver.py which asks a human if they want to play first or second. It then accepts human inputs of moves in the above format, and outputs between moves the history so far. It should also detect if the game is over and say who wins.

That is the description of the homework.

Point Breakdown